#include "string_array.h"

using namespace std;

myStr::myStr(const char* a){
    length= 0;
    data = new char[255];
    next = new int[255];
    nextVal = new int[255];
    while(*a){
      data[length] = *a;
      a++;
      length++;
    }
}

myStr::~myStr(){
    delete []data;
    delete []next;
    delete []nextVal;
}

int simpleMatch(const myStr& S, const myStr& T){

    int T_len = T.length;

    int S_len = S.length;

    int i = 0,j = 0;

    while(i <= S_len - T_len){

        j = i;

        while((S.data[j] == T.data[j - i]) && (j - i  < T_len))
            j++;

        if(j - i  == T_len)
            return (i+1);

        i++;

    }

    return -1;
}

int kmpMatch(const myStr& S, const myStr& T){

    int T_len = T.length;

    int S_len = S.length;

    int i = 0,j = 0;

    while(i <= S_len - T_len){

        j = i;

        while((S.data[j] == T.data[j - i]) && (j - i  < T_len))
            j++;

        if(j - i  == T_len)
            return (i+1);

        i++;

    }

    return -1;
}

bool replaceStr(myStr& S, const int& start, const myStr& T, const myStr& V){

    int T_len = T.length;

    int S_len = S.length;

    int V_len = V.length;

    int i = start-1 ,j = 0 , station = -1;

    while(i <= S_len - T_len){

        j = i;

        while((S.data[j] == T.data[j - i]) && (j - i  < T_len))
            j++;

        if(j - i  == T_len){
            station = i ;
            break;
        }

        i++;

    }

    if(station == -1)
        return 0;

    if(V_len > T_len){

        S.length = S_len + V_len - T_len;

        i = S.length - 1;

        while(i >= station + V_len ){

            S.data[i] = S.data[i-V_len+T_len];

            i--;

        }


    }
        else if(V_len < T_len){

            S.length = S_len + V_len - T_len;

            i =  station + V_len;

            while(i < S.length){

                S.data[i] = S.data[i-V_len+T_len];

                i++;

            }

        }

        for(i = station; i < station + V_len ; i++)
            S.data[i] = V.data[i - station];

    return 1;
}

void myStr::kmp_next(){
    next[0]=0;
	for(int i =1;i<length;i++){
		if(i==1){
			if (data[1]==data[0]) next[1]=1;
			else next[1]=0;
		}
		if(data[i]==data[next[i-1]]) next[i]=next[i-1]+1;
		else if (data[i]==data[0]) {
			next[i]=1;
		}
		else{
			next[i]=0;
		}
	}
	for(int i =length-1;i>0;i--){
		next[i]=next[i-1]+1;
	}

}

void myStr::kmp_nextVal(){
    nextVal[0]=0;
    for(int i =1;i<length;i++){
        nextVal[i]=(data[i] == data[next[i]-1])?nextVal[next[i]-1]:next[i];

    }




}

void myStr::print(){
    for(int i = 0; i < this->length; i++)
        cout << this->data[i];

    cout << endl;
}

void myStr::printNext(){
    for(int i = 0; i < length; i++)
        cout << next[i];
    cout << endl;
}

void myStr::printNextVal(){
    for(int i = 0; i < length; i++)
        cout << nextVal[i];
    cout << endl;
}

myMatrix::myMatrix(const int& rnum, const int& cnum, const int& nnum, const int* arr){

    int a[nnum];

    nodeList = new matrixNode[10];

    rowNum = rnum;

    colNum = cnum;

    nodeNum = nnum;

    int nmin , cmin;

    for(int i = 0; i < nnum; i++)
        a[i] = 1;

    for(int j = 0; j < nnum;j++){

        nmin = 20;

        cmin = 20;

        for(int i = 0; i < nnum; i++)
            if(a[i] && nmin > arr[3*i])nmin = arr[3*i];

        for(int i = 0; i < nnum; i++)
            if(a[i] && nmin == arr[3*i] && cmin > arr[3*i + 1])cmin = arr[3*i + 1];

        for(int i = 0; i < nnum; i++){

            if(a[i] && nmin == arr[3*i] && cmin == arr[3*i + 1]){

                nodeList[j].row = arr[3*i];

                nodeList[j].col = arr[3*i + 1];

                nodeList[j].value = arr[3*i + 2];

                a[i] = 0;

                break;
            }

        }

    }

}

myMatrix::myMatrix(){

    nodeList = new matrixNode[10];

}

myMatrix::~myMatrix(){
    delete []nodeList;
}

void myMatrix::FastTransposeSMatrix(myMatrix& t){

    t.rowNum = this->colNum;

    t.colNum = this->rowNum;

    t.nodeNum = this->nodeNum;

    int arr[30],a[10];

    for(int i = 0; i < nodeNum; i++){

        arr[3*i] = nodeList[i].col;

        arr[3*i + 1] = nodeList[i].row;

        arr[3*i + 2] = nodeList[i].value;

        a[i] = 1;

    }

    int nnum = nodeNum, nmin, cmin;

        for(int j = 0; j < nnum;j++){

        nmin = 20;

        cmin = 20;

        for(int i = 0; i < nnum; i++)
            if(a[i] && nmin > arr[3*i])nmin = arr[3*i];

        for(int i = 0; i < nnum; i++)
            if(a[i] && nmin == arr[3*i] && cmin > arr[3*i + 1])cmin = arr[3*i + 1];

        for(int i = 0; i < nnum; i++){

            if(a[i] && nmin == arr[3*i] && cmin == arr[3*i + 1]){

                t.nodeList[j].row = arr[3*i];

                t.nodeList[j].col = arr[3*i + 1];

                t.nodeList[j].value = arr[3*i + 2];

                a[i] = 0;

                break;
            }

        }

    }

}

void myMatrix::printMatrix(){
    cout << rowNum << "," << colNum << "," << nodeNum << endl;

    for(int i = 0; i < nodeNum; i++)
        cout << nodeList[i].row << "," << nodeList[i].col << "," << nodeList[i].value << endl;
}
